/*
 * @lc app=leetcode.cn id=127 lang=cpp
 *
 * [127] 单词接龙
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool isAdj(const string &l, const string &s)
    {
        bool ret = false;
        for (int i = 0; i < l.length(); i++)
        {
            if (l[i] != s[i])
            {
                if (ret)
                    return false;
                else
                    ret = true;
            }
        }
        return ret;
    }

    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        set<string> words;
        for (auto &&s : wordList)
            words.insert(s);

        int curr = 0;
        set<string> q[2];
        q[curr].insert(beginWord);

        int ret = 0;
        bool find = false;
        while (q[curr].size() && !find)
        {
            ret++;

            for (auto &s : q[curr])
            {
                words.erase(s);

                if (s == endWord)
                {
                    find = true;
                    break;
                }

                for (auto &ss : words)
                {
                    if (isAdj(s, ss))
                    {
                        q[1-curr].insert(ss);
                    }
                }
            }

            q[curr].clear();
            curr = 1 - curr;
        }

        return find ? ret : 0;
    }
};
// @lc code=end
